package sliding_window

/*
862.给你一个【整数数组】 nums 和一个整数 k ，找出 nums 中和【至少为 k】 的 【最短】非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。

示例 1：
输入：nums = [1], k = 1
输出：1

示例 2：
输入：nums = [1,2], k = 4
输出：-1

示例 3：
输入：nums = [2,-1,2], k = 3
输出：3

*/

/*
	Calculate prefix sum B of list A.
    B[j]-B[i] represents the sum of subarray A[i]~A[j-1]
    CustomQueue d will keep indexes of increasing B[i]
    For every B[i],we will compare B[i]-B[d[0]] wit K.
	Time O(N)
	Space O(N)
*/
func shortestSubarray(nums []int, k int) int {
	right, n := 0, len(nums)
	res := n + 1
	b := make([]int, n+1)

	//构造前缀和
	for i := 0; i < n; i++ {
		b[i+1] = b[i] + nums[i]
	}
	q := newDeque()
	for right < n+1 {
		for q.size() > 0 && b[right]-b[q.getFirst()] >= k { //最小前缀和
			res = min(res, right-q.popFirst()) //已经找到，最后drop掉
		}
		//保持队列增加，下标right始终是大于q.getLast的
		for q.size() > 0 && b[right] <= b[q.getLast()] {
			q.popLast()
		}

		q.push(right)
		right++
	}
	if res > n {
		res = -1
	}
	return res
}
